package com.coder.algorithm.offer_2;

import com.coder.algorithm.struct.ListNode;

/**
 * 两个链表的第一个公共节点
 *
 * @author yuhushuan
 * @date 2020/6/29 10:29
 */
public class _52_1_FirstCommonNodesInLists {
    private static ListNode findFirstCommonNode(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        int length1 = getListLength(head1);
        int length2 = getListLength(head2);

        int diffLength = 0;
        ListNode headLong;
        ListNode headShort;
        if (length1 > length2) {
            diffLength = length1 - length2;
            headLong = head1;
            headShort = head2;
        } else {
            diffLength = length2 - length1;
            headLong = head2;
            headShort = head1;
        }

        // 先在长链表上走几步，在同时在两个链表上遍历
        for (int i = 0; i < diffLength; ++i) {
            headLong = headLong.getNext();
        }

        while (headLong != null && headShort != null && headLong != headShort) {
            headLong = headLong.getNext();
            headShort = headShort.getNext();
        }
        // 得到第一个公共节点
        ListNode firstCommonNode = headLong;
        return firstCommonNode;
    }

    private static int getListLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.getNext();
        }
        return length;
    }

    public static void main(String[] args) {
        // 功能测试
        // 有公共点：公共点在链表的中间
        // 有公共点：公共点在链表的末尾
        // 有公共点：公共点在链表的头节点
        // 没有公共点

        // 特殊输入测试

    }
}
